package com.formula.datastructure.exam.tree;

import com.formula.datastructure.util.DataUtil;

public class HuffmanTree {

    private HuffmanNode[] nodes;

    public void buildTree(Integer[] array) {
        int N = array.length;
        nodes = new HuffmanNode[2 * N - 1];
        for (int i = 0; i < N; i++) {
            nodes[i] = new HuffmanNode(array[i]);
        }

        int start = 0;
        int last = N - 1;

        while (last < 2 * N - 2) {
            sort(start, last);
            HuffmanNode a = nodes[start];
            HuffmanNode b = nodes[start + 1];

            HuffmanNode parent = new HuffmanNode(a.weight + b.weight);
            parent.left = a;
            parent.right = b;

            nodes[++last] = parent;

            a.parent = parent;
            b.parent = parent;

            start = start + 2;
        }
    }

    public HuffmanNode[] genCode() {
        HuffmanNode root = nodes[nodes.length - 1];
        root.genCode("");
        return nodes;
    }

    private void sort(int first, int last) {
        Integer min;
        HuffmanNode temp;
        for (int i = first; i <= last; i++) {
            min = 99999;
            int idx = i;
            for (int j = i; j <= last; j++) {
                if (min > nodes[j].weight) {
                    min = nodes[j].weight;
                    idx = j;
                }
            }
            if (idx != i) {
                temp = nodes[i];
                nodes[i] = nodes[idx];
                nodes[idx] = temp;
            }
        }
    }

    public static void main(String[] args) {
        HuffmanTree huffmanTree = new HuffmanTree();

        int size = 10;
        int range = 99;
        Integer[] array = DataUtil.genUniqueArray(size, range);
        DataUtil.printIndex(size);
        DataUtil.printArray(array);

        huffmanTree.buildTree(array);
        huffmanTree.genCode();
        System.out.println();
    }

}
